package isBalanced

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// 判断一颗树是否是AVL树
func isBalanced(root *TreeNode) bool {
	if root == nil {
		return true
	}
	var balance func(node *TreeNode) int
	balance = func(node *TreeNode) int {
		if node == nil {
			return 0
		}
		//  后序遍历才能知道当前结点的最大高度
		leftHeight := balance(node.Left)
		rightHeight := balance(node.Right)

		// 子树不是AVL那么，以当前结点为根结点的树也不会是AVL树
		if leftHeight == -1 || rightHeight == -1 || abs(leftHeight-rightHeight) > 1 {
			return -1
		}

		// 返回子树的最大高度
		return max(leftHeight, rightHeight) + 1
	}
	return balance(root) > 0
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func abs(a int) int {
	if a < 0 {
		return -1 * a
	}
	return a
}
